記錄學習內容。看網路上大大們的文章和影片，做些紀錄。
以下內容大多來自網路上大大們的文章。截圖也來自文章和影片。
還不了解，內容可能有錯誤。

5.4.4 Bellman Ford Algorithm - Single Source Shortest Path - Dynamic Programming
https://www.youtube.com/watch?v=FtN3BYH2Zes&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=53&ab_channel=AbdulBari

[演算法] 最短路徑 (Bellman-Ford 演算法)
https://ithelp.ithome.com.tw/articles/10209748

假設有5個邊 ，有4個點 ，那就是執行(4個點-1=3 ) 次的 所有邊長(5個邊長)的鬆弛

看程式:

Bellman–Ford Algorithm | DP-23
https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/
第1步 ，先用一個陣列 ，代表1 號(起點，src)到 其他點 的 最短距離 。

第2步 ，第一層迴圈 ，代表跑 (點-1) 次 的迴圈
第二層迴圈 ， 就是去 Relax 所有的邊 ，
如果 (目前1 號 到起點 的最短距離) + (起點 到 終點 邊的距離) < 目前 1 號 到 終點的最短距離 。
那 目前 1 號 到 終點的最短距離 就會更新，變得更小。

這個演算法 可以解決前面的Dijkstra Algorithm 有負數邊長的問題 。

Floyd-Warshall 、Dijkstra Algorithm 筆記
https://ithelp.ithome.com.tw/articles/10238059

用Bellman–Ford Algorithm ，可以在有負數邊長的狀況 ，答案正確。

然後有講到 怎麼偵測 負權迴路(Negative Cycles) 。

因為負權迴路(Negative Cycles) 就是會 越走越小 。如果我們繼續觀察每條邊，
還是會發現 ， 有些邊可以繼續 relax 。那就是有負權迴路(Negative Cycles)

最短路徑 (Bellman-Ford 演算法 - 佇列優化)

[演算法] 最短路徑 (Bellman-Ford 演算法 - 佇列優化)
https://ithelp.ithome.com.tw/articles/10209845

有一種優化的方式 :

原本是只選了一個起點(1號) ，之後對每條邊不斷relax。

現在改成 1號當起點 ，第一輪對1相鄰的邊進行鬆弛 後 ，有 鬆弛成功
，就代表 1 號 到 某個點 的距離 變短了 。

這些成功的點 放進 佇列 。

佇列裡成功的點 在一個一個 鬆弛

如果佇列裡沒有點了。代表:鬆弛失敗 ，程式該結束了。

貝爾曼-福特演算法
https://zh.wikipedia.org/wiki/%E8%B4%9D%E5%B0%94%E6%9B%BC-%E7%A6%8F%E7%89%B9%E7%AE%97%E6%B3%95

最壞時間複雜度 : 因為 第一層迴圈 是 點 ，第二層迴圈是邊 ，所以點 * 邊

最佳複雜度 ， 就想(Bellman-Ford 演算法 - 佇列優化) 的方法 。
因為 第一次鬆弛 後 ，發現沒有 更短的距離了 。佇列是空的 ，程式就結束了 。 所以只跑一次 ，時間複雜度 就是 邊長的個數